package leetcode_day._2021._202112._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/11 20:13
 * 在线选举
 * 给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
 * 对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
 * 在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
 * 实现 TopVotedCandidate 类：
 * TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
 * int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。
 * 算法：二分查找
 * 计算 time[i] 时领先的候选人
 * 用二分查找找到 t 时刻领先的候选人
 */
public class _11_911 {
    class TopVotedCandidate {
        // ans: 记录 times[i] 时刻，选票最多的人
        int[] ans, times;

        public TopVotedCandidate(int[] persons, int[] times) {
            this.times = times;
            int len = persons.length;
            ans = new int[len];
            // 记录当前候选人的票数
            int[] personNums = new int[len];
            // 当前领先的候选人
            int cnt = -1;
            for (int i = 0; i < len; i++) {
                int person = persons[i];
                ++personNums[person];
                if (cnt == -1 || personNums[person] >= personNums[cnt]) cnt = person;
                ans[i] = cnt;
            }
        }

        public int q(int t) {
            int l = 0, r = times.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (t >= times[mid]) l = mid;
                else r = mid - 1;
            }
            return times[l] <= t ? ans[l] : 0;
        }
    }

}
